import java.io.BufferedWriter;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.LinkedList;

public class DFA {

	ArrayList<DState> table;

	DState current;
	
	DState start;

	static final int NUM_CHAR = 256;

	private DFA() {
		table = new ArrayList<DState>();

	}

	public DState addState(DState state) {

		if (table.isEmpty()) {
			start = state;
			current = start;
		}

		table.add(state);

		return state;
	}

	public DState addEmptyState() {
		DState state = new DState();

		if (table.isEmpty()) {
			start = state;
		}

		table.add(state);

		return state;
	}

	public DState findMatchingState(ArrayList<State> s) {

		for (int i = 0; i < table.size(); i++) {
			if (table.get(i).checkEquality(s))
				return table.get(i);
		}

		return addState(new DState(s));

	}

	public DState addMove(DState d, int c, ArrayList<State> s) {

		current = start;
		DState n = findMatchingState(s);
		d.addTransition(c, c, n);
		return n;

	}

	public void addTransition(int startIndex, int endIndex,
			DState destinationState) {
		addTransition(startIndex, endIndex, destinationState, table.size() - 1);
	}

	public void addTransition(int startIndex, int endIndex,
			DState destinationState, int id) {
		table.get(id).addTransition(startIndex, endIndex, destinationState);
	}

	public int getSize() {
		return table.size();
	}

	public String match(String s, ScannerGenerator sg) {

		DState curr = start;
		for (int i = 0; i < s.length(); i++) {
			if (curr.getNext(s.charAt(i)) == null) {
				return "";
			}
			curr = curr.getNext(s.charAt(i));
		}

		if (curr.getTokenNames().size() == 0) {
			return "";
		}
		ArrayList<String> a =curr.getTokenNames();
		int maxn=0;
		
		if(a.size()>1){
			int minp=999999;
			
			int k;
			for(int i=0; i<a.size(); i++){
				k=sg.getRule(a.get(i)).getPriority();
				if(k<minp){
					maxn=i;
					minp=k;
				}
			}
			
		}
		
		
		return a.get(maxn);

	}

	public void increment(int n) {
		for (int i = 0; i < table.size(); i++) {
			table.get(i).setId(table.get(i).getId() + n);
		}

	}

	public DState getState(int id) {
		return table.get(id);
	}

	public static DFA produceDFA(ArrayList<Rule> r) {

		ArrayList<NFA> n = new ArrayList<NFA>();

		ArrayList<State> startingStates = new ArrayList<State>();

		for (int i = 0; i < r.size(); i++) {
			if(r.get(i).isToken()){
				n.add(r.get(i).getNFANoCopy());
	
				r.get(i).getNFANoCopy().fixAccepting();
				startingStates.addAll(NFA
						.emptyClosure(r.get(i).getNFANoCopy().getStart()));
			}
		}

		DFA d = new DFA();

		DState curr = d.addState(new DState(startingStates));

		DState temp = null;

		ArrayList<State> test;

		LinkedList<DState> waiting = new LinkedList<DState>();
		LinkedList<DState> finished = new LinkedList<DState>();

		waiting.add(curr);

		while (!waiting.isEmpty()) {
			curr = waiting.peek();
			//System.out.println(curr.getNFAStates().size());
			for (int i = 1; i < NUM_CHAR; i++) {
				test = NFA
						.emptyClosure(NFA.moveFunction(curr.getNFAStates(), i));

				temp = d.addMove(curr, i, test);

				for (int k = 0; k < test.size(); k++) {
					//System.out.println(test.get(k).getId());
				}

				if (!waiting.contains(temp) && !finished.contains(temp)) {
					waiting.addLast(temp);
				}
			}
			finished.add(waiting.pop());
		}

		return d;
	}

	public void printDFA() {

		int c2 = 0;
		ArrayList<String> s;
		for (int i = 0; i < table.size(); i++) {
			for (int j = 0; j < NUM_CHAR; j++) {

				c2 = table.get(i).getNext(j).getId();
				if (c2 != 0)
					System.out.println("State " + table.get(i).getId()
							+ " connected to "
							+ table.get(i).getNext(j).getId() + " starting at "
							+ j);
			}
			s = table.get(i).getTokenNames();
			if (s.size() != 0) {
				System.out.print(table.get(i).getId() + " accepts: ");
				for (int k = 0; k < s.size(); k++) {
					System.out.print(" " + s.get(k));
				}
				System.out.print("\n");
			}
		}
	}

	public void printTable() {

		int[][] t = generateDFATable();

		System.out.print("     ");

		for (int k = 32; k < 128; k++) {
			System.out.print((char) k);
			System.out.print("    ");
		}
		System.out.print("\n");
		ArrayList<String> tokens;
		for (int i = 0; i < table.size(); i++) {
			if (i == 0) {
				System.out.print("0    ");
			} else {
				printNumber(i);
			}
			for (int k = 32; k < 128; k++) {
				printNumber(t[i][k]);
			}
			tokens = table.get(i).getTokenNames();
			
			if(tokens.size()>0)
				System.out.print(tokens.get(tokens.size()-1)+"\n");
			else
				System.out.print("\n");
		}
	}

	private static void printNumber(int i) {

		int space = (int) (5 - Integer.toString(i).length());
		System.out.print(i);
		for (int k = 0; k < space; k++) {
			System.out.print(" ");
		}
	}

	public int[][] generateDFATable() {
		int[][] result = new int[table.size()][NUM_CHAR];

		DState curr;
		for (int i = 0; i < table.size(); i++) {
			curr = table.get(i);
			for (int k = 0; k < NUM_CHAR; k++) {
				result[i][k] = indexOf(curr.getNext(k));
			}
		}
		return result;
	}

	private int indexOf(DState d) {

		for (int i = 0; i < table.size(); i++) {
			if (table.get(i) == d)
				return i;
		}
		return -1;
	}

	public void writeTableToFile(String s) {

		int[][] t = generateDFATable();

		try {
			// Create file
			FileWriter fstream = new FileWriter(s);
			BufferedWriter out = new BufferedWriter(fstream);
			
			for(int i=0;i<t.length; i++){
				for(int k=1;k<t[i].length; k++){
					out.write(Integer.toString(t[i][k]));
					out.write(",");
				}
				out.write(";\n");
			}
			
			// Close the output stream
			out.close();
		} catch (Exception e) {// Catch exception if any
			System.err.println("Error: " + e.getMessage());
		}
	}

	public void step(int k) {
		current = current.getNext(k);
	}

	public String getPoss() {
		ArrayList<String> s = current.getTokenNames();
		if(s.isEmpty()){
			return null;
		}
		return s.get(s.size()-1);
		
	}
	
	public String peek(int k){
		DState temp = current;
		temp = current.getNext(k);
		if(temp==null)
			return null;
		ArrayList<String> s = temp.getTokenNames();
		if(s.isEmpty()){
			return null;
		}
		return s.get(s.size()-1);
		
	}

	public void reset() {
		current = start;
	}
	
	
	

}
